package com.ztom.top100;

/**
 * 最佳买卖股票时机含冷冻期
 * <p>
 * https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/
 *
 * @author ZhangTao
 */
public class Code78MaxProfit {

    public static class Info {
        /**
         * 第 i 天没有持股, 且没有卖
         * 可能是昨天也没有持股 或 昨天卖了今天冷冻期
         */
        private int p1;
        /**
         * 第 i 天卖了所以没有持股
         * 昨天一定持股没卖
         */
        private int p2;
        /**
         * 第 i 天持股
         * 可能是昨天持股没卖 或 昨天不持股也没卖, 今天买了
         */
        private int p3;

        public Info(int p1, int p2, int p3) {
            this.p1 = p1;
            this.p2 = p2;
            this.p3 = p3;
        }
    }

    public int maxProfit2(int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }

        Info info = process(prices, prices.length - 1);
        // 最后一天手里还持股, 没有意义
        return Math.max(info.p1, info.p2);
    }

    private Info process(int[] prices, int i) {
        if (i == 0) {
            // 第一天
            return new Info(0, 0, -prices[0]);
        }
        // 昨天的情况
        Info yesterday = process(prices, i - 1);
        // 今天没持股也没卖: 昨天也没持股也没卖 或 昨天卖了今天冷冻期
        int p1 = Math.max(yesterday.p1, yesterday.p2);
        // 今天没持股且卖了: 昨天持股, 今天卖了
        int p2 = yesterday.p3 + prices[i];
        // 今天持股: 昨天没持股也没卖, 今天买的  或 昨天持股
        int p3 = Math.max(yesterday.p1 - prices[i], yesterday.p3);
        return new Info(p1, p2, p3);
    }

    public int maxProfit1(int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }

        int n = prices.length;
        int[][] dp = new int[n][3];
        // 第一天没买没卖
        dp[0][0] = 0;
        // 第一天买了又卖
        dp[0][1] = 0;
        // 第一天买了不卖
        dp[0][2] = -prices[0];

        for (int i = 1; i < n; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1]);
            dp[i][1] = dp[i - 1][2] + prices[i];
            dp[i][2] = Math.max(dp[i - 1][0] - prices[i], dp[i - 1][2]);
        }
        return Math.max(dp[n - 1][0], dp[n - 1][1]);
    }

    /**
     * 空间压缩
     *
     * @param prices
     * @return
     */
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }

        int n = prices.length;
        // 第一天没买没卖
        int p1 = 0;
        // 第一天买了又卖
        int p2 = 0;
        // 第一天买了不卖
        int p3 = -prices[0];

        for (int i = 1; i < n; i++) {
            int tmp1 = p1;
            int tmp2 = p2;
            int tmp3 = p3;
            p1 = Math.max(tmp1, tmp2);
            p2 = tmp3 + prices[i];
            p3 = Math.max(tmp1 - prices[i], tmp3);
        }
        return Math.max(p1, p2);
    }
}
